package Lee_code;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * @author blh
 * @date 2024年07月09日 11:13
 */
public class Lee_40_79 {
    HashSet<List<Integer>> res = new HashSet<>();
    int end;
    int len;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        end = target;
        len = candidates.length;
        Arrays.sort(candidates);
        traceBack(0, 0,new ArrayList<>(), candidates);
        return new ArrayList<>(res);
    }

    private void traceBack(int index, int sum, ArrayList<Integer> list, int[] candidates) {
        if (sum == end) {
            res.add(new ArrayList<>(list));
            return;
        } else if (sum > end) {
            return;
        }
        // 开始回溯
        for (int i = index; i < len; i++) {
            if (i>index && candidates[i]==candidates[i-1]){
                continue;
            }
            list.add(candidates[i]);
            traceBack(i+1, sum + candidates[i],list, candidates);
            list.remove(list.size() - 1);
        }
    }
}
